class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> sum;

        // 没有数据  1个数据 2个数据
        if (nums.size() == 0 || nums.size() == 1 || nums.size() == 2)
            return sum;

        // 先排升序
        sort(nums.begin(), nums.end());
        for (int cur = 0; cur <= nums.size() - 3; )   // 最后一组是cur == nums.size() - 3
        {
            // 先固定cur
            // 前后指针
            int left = cur + 1, right = nums.size() - 1;

            while (left < right)
            {
                if (nums[left] + nums[right] == (-nums[cur]))  // 找相反数
                {
                    sum.push_back({ nums[cur], nums[left], nums[right] });

                    // 去重，相同的left和right跳过
                    while (left < right)
                    {
                        if (nums[left] == nums[left + 1])
                            left++;

                        if (nums[right] == nums[right - 1])
                            right--;

                        // 只有left和right都没有重复元素，才跳出循环
                        // 注意：left不能越界
                        if(left < nums.size() - 1)
                        {
                            if (nums[left] != nums[left + 1] && nums[right] != nums[right - 1])
                                break;
                        }
                    }

                    left++; right--;    // 没有重复，就同时进行
                }
                else if (nums[left] + nums[right] < (-nums[cur]))
                {
                    left++;
                }
                else
                {
                    right--;
                }
            }

            // cur去重
            while (cur <= nums.size() - 3)
            {
                if (nums[cur] == nums[cur + 1])
                {
                    cur++;  // 相同就cur往后一直走
                }
                else
                {
                    cur++;  // 不相同cur往后走一步
                    break;
                }
            }

            // 优化cur，nums[cur]大于0，后面就不用看了
            if(nums[cur] > 0)
                break;
        }

        return sum;
    }
};